#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INV2 = (MOD + 1)/2;
const int LMT = 1e7+10;
int g[LMT];
int minP[LMT];
int PA[LMT];
const int K = 1e5+10;
int a[K];
const int N = 2010;
int P[N];
int num[N][N];
int nums[N];
int F[N][N];
int qpow(int x,int p,int mod){
    int res = 1;
    while(p){
        if(p & 1){
            res = 1ll*res*x%mod;
        }
        x = 1ll*x*x%mod;
        p >>= 1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    int n,k;
    cin>>n>>k;
    int ma = 0;
    for(int i = 0;i < k;i++){
        cin>>a[i];
        ma = max(a[i],ma);
    }
    vector<int> p;
    for(int i = 2;i <= ma;i++){
        if(!minP[i]){
            minP[i] = i;
            PA[i] = i;
            p.push_back(i);
        }
        for(int j = 0;1ll*p[j]*i <= ma && p[j] != minP[i];j++){
            minP[i * p[j]] = p[j];
            PA[i * p[j]] = p[j];
        }
        if(1ll*i*minP[i] <= ma){
            PA[i * minP[i]] = PA[i] * minP[i];
            minP[i * minP[i]] = minP[i];
        }
    }
/*
try by myself
for k = 0
%p!=1 && %p!=0
p^(a - 1) * (p - 2)
%p^k=1 && %p^{k + 1}!=1
p^{a - k - 1}(p - 1)*p^k
(a - 1)p^{a - 1}*(p - 1)
p^a
p^{a - 1}(p + p - 2 + (a - 1)*(p - 1)) = 
p^{a - 1}a(p - 1)
p^{a - 1}(a + 1)(p - 1)
*/
    for(int i = 2;i <= ma;i++){
        if(i == minP[i]){
            g[i] = 2*i - 2;
        }else if(i == PA[i]){
            g[i] = 1ll*(1ll*g[i/minP[i]]*minP[i]%MOD + i/minP[i]*(minP[i] - 1))%MOD;
        }else{
            g[i] = 1ll*g[i/PA[i]]*g[PA[i]]%MOD;
        }
    }
    g[1] = 1;
    for(int i = 0;i<k;i++){
        a[i] = g[a[i]];
    }
    P[1] = 1;
    P[0] = 1;
    for(int i = 2;i<=n;i++){
        for(int j = 1;1ll*j*(3*j - 1)/2 <= i;j++){
            if(j & 1){
                P[i] = (P[i] + P[i - j*(3*j - 1)/2])%MOD;
                if(j*(3*j + 1)/2 <= i){
                    P[i] = (P[i] + P[i - j*(3*j + 1)/2])%MOD;    
                }
            }else{
                P[i] = (P[i] + MOD - P[i - j*(3*j - 1)/2])%MOD;
                if(j*(3*j + 1)/2 <= i){
                    P[i] = (P[i] + MOD - P[i - j*(3*j + 1)/2])%MOD;    
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        if(t == 1){
            F[i][i] = 1;
        }else if(t == 2){
            F[i][i] = __gcd(i,i);
        }else{
            F[i][i] = ((qpow(i,i,k) + qpow(i,i,k))%k + (i^i))%k;
        }
        for(int j = 1;i * j <= n;j++){
            nums[j] = P[n - i*j];
        }
        for(int j = 1;i * j <= n;j++){
            nums[j] = (nums[j] - nums[j + 1] + MOD)%MOD;
            ans = (ans + 1ll*nums[j]*j%MOD*(j - 1)%MOD*INV2%MOD*a[F[i][i]]%MOD)%MOD;
        }
        for(int j = 1;i * j <= n;j++){
            nums[j] = 0;
        }
        for(int j = 1;j < i;j++){
            if(t == 1){
                F[i][j] = 1;
            }else if(t == 2){
                F[i][j] = __gcd(i,j)%k;
            }else{
                F[i][j] = ((qpow(i,j,k) + qpow(j,i,k))%k + (i^j))%k;
            }
            for(int k = 1;k * i <= n;k++){
                for(int l = 1;l * j <= n - k*i;l++){
                    num[k][l] = P[n - k*i - l*j];
                }
            }

            for(int k = 1;k * i <= n;k++){
                for(int l = 1;l * j <= n - k*i;l++){
                    num[k][l] = ((num[k][l] + (MOD - num[k][l + 1])%MOD)%MOD + ((MOD - num[k + 1][l])%MOD + num[k + 1][l + 1])%MOD)%MOD;
                    ans = (ans + 1ll*num[k][l]*k%MOD*l%MOD*a[F[i][j]]%MOD)%MOD;
                }
            }
            for(int k = 1;k * i <= n;k++){
                for(int l = 1;l * j <= n - k*i;l++){
                    num[k][l] = 0;
                }
            }
            
        }
    }
    cout<<ans<<'\n';
}